// 字符串匹配自动机
// 后缀函数: 模式P的前缀=需匹配字符串的后缀，P的最长前缀长度。

// 构造模式P的状态转移函数，模式P={1, 2, ..., m} 有m个字符，字符集E是P中出现的所有字符
// 状态转移函数用一个二维数组表示，第一维表示状态Q={0, 1, 2, ..., m}，其中0是初始状态，m是接受状态
// 第二维表示字符，将所有字符在一个字符串中列出，字符在其中的位置用来代表该字符

#include <stdlib.h>
#include <string.h>
#include "includes/mydfa.h"

mydfa *mydfa_create(char *p) {
    mydfa *d = malloc(sizeof(mydfa));
    int p_len = strlen(p);
    char *cs = calloc(p_len, 1);
    int cs_len = 0;
    for (int i = 0; i < p_len; i++)
    {
        if(!strchr(cs, p[i])) {
            cs[cs_len++] = p[i];
        }
    }
    
    int *t = calloc(p_len * cs_len, sizeof(int));
    for (int i = 0; i < p_len; i++) // i表示当前状态
    {
        printf("[mydfa_create] start state %d\n", i);
        for (int j = 0; j < cs_len; j++) // j表示下一个字符
        {
            char *pi_c = calloc(i + 2, 1);
            if(i > 0) strncat(pi_c, p, i);
            *(pi_c + i) = cs[j];
            printf("[mydfa_create] start state %d, char %c, pci: %s\n", i, cs[j], pi_c);
            for (int k = i + 1; k >= 0; k--) // k表示目标状态
            {
                printf("[mydfa_create] start state %d, char %c, pci: %s, next state %d\n", i, cs[j], pi_c, k);
                if(strncmp(p, pi_c + i + 1 - k, k) == 0) {
                    printf("[mydfa_create] start state %d, char %c, pci: %s, next state %d, matched\n", i, cs[j], pi_c, k);
                    t[MYDFA_IDX(i, j, cs_len)] = k;
                    break;
                }
            }
        }
    }
    
    d->pattern = p;
    d->charset = cs;
    d->pattern_len = p_len;
    d->charset_len = cs_len;
    d->transition = t;
    return d;
}

// 返回模式在字符串中的位置，-1表示失败
int mydfa_match(mydfa *d, char *s) {
    int s_len = strlen(s);
    int q = 0;
    for (int i = 0; i < s_len; i++)
    {
        int j = strchr(d->charset, s[i]) - d->charset;
        q = d->transition[MYDFA_IDX(q, j, d->charset_len)];
        printf("[mydfa_match] %d. %c, next state: %d\n", i, s[i], q);
        if(q == d->pattern_len) {
            printf("[mydfa_match] find\n");
            return i - d->pattern_len + 1;
        }
    }
    return -1;
}
